/*
 * @Author: 0x9DEFA478
 * @Date: 2025-07-19 15:16:10
 * @LastEditTime: 2025-07-27 00:37:47
 * @LastEditors: 0x9DEFA478
 * @Description: 
 * 
 */
#include "./H_Tree.h"
#include "H_Type.h"




H_TreeNode* H_Tree_FrontNode(H_TreeNode* Root){
  H_TreeNode* Node;
  H_TreeNode* Left;

  Node=Root;
  if(Node==NULL){
    return NULL;
  }
  while((Left=Node->Left)!=NULL){
    Node=Left;
  }
  return Node;
}

H_TreeNode* H_Tree_BackNode(H_TreeNode* Root){
  H_TreeNode* Node;
  H_TreeNode* Right;

  Node=Root;
  if(Node==NULL){
    return NULL;
  }
  while((Right=Node->Right)!=NULL){
    Node=Right;
  }
  return Node;
}

H_TreeNode* H_Tree_Forward(H_TreeNode* Node){
  H_TreeNode* Right;
  H_TreeNode* Parent;

  if(Node==NULL){
    return NULL;
  }

  Right=Node->Right;
  if(Right!=NULL){
    return H_Tree_FrontNode(Right);
  }

  Parent=Node->Parent;
  while((Parent!=NULL)&&(Parent->Right==Node)){
    Node=Parent;
    Parent=Node->Parent;
  }

  return Parent;
}

H_TreeNode* H_Tree_Backward(H_TreeNode* Node){
  H_TreeNode* Left;
  H_TreeNode* Parent;

  if(Node==NULL){
    return NULL;
  }

  Left=Node->Left;
  if(Left!=NULL){
    return H_Tree_BackNode(Left);
  }

  Parent=Node->Parent;
  while((Parent!=NULL)&&(Parent->Left==Node)){
    Node=Parent;
    Parent=Node->Parent;
  }

  return Parent;
}

H_TreeNode* H_Tree_FirstFree(H_TreeNode* Root){
  H_TreeNode* L;
  H_TreeNode* R;
  H_TreeNode* CL;
  H_TreeNode* CR;

  if(Root==NULL){
    return NULL;
  }

  L=Root->Left;
  R=Root->Right;
  for(;;){
    
    if(L!=NULL){
      CL=L->Left;
      CR=L->Right;
      if((CL!=NULL)||(CR!=NULL)){
        Root=L;
        L=CL;
        R=CR;
        continue;
      }
    }

    if(R!=NULL){
      CL=R->Left;
      CR=R->Right;
      if((CL!=NULL)||(CR!=NULL)){
        Root=R;
        L=CL;
        R=CR;
        continue;
      }
    }

    break;
  }

  return Root;
}

H_TreeNode* H_Tree_NextFree(H_TreeNode* Node){
  H_TreeNode* Parent;
  if(Node==NULL){
    return NULL;
  }

  Node->Left=NULL;
  Node->Right=NULL;

  Parent=Node->Parent;
  if(Parent==NULL){
    return Node;//仅作为保护措施, 使用者不应该依赖这个特性
  }

  return H_Tree_FirstFree(Parent);
}



